package com.lw.leetcode.bit.b;

/**
 * Created with IntelliJ IDEA.
 * 1017. 负二进制转换
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/25 10:29
 */
public class BaseNeg2 {

    public static void main(String[] args) {
        BaseNeg2 test = new BaseNeg2();

        // 11010
        int n = 6;

        // 10010
//        int n = 14;

        for (int i = 1; i < 10000; i++) {
            String s = test.baseNeg2(i);
            String s1 = test.baseNeg21(i);

            if (!s.equals(s1)) {
                System.out.println(i + "   " + s + "   " + s1);
            }
        }
        System.out.println("OK");
    }

    public String baseNeg2(int n) {
        char[] arr = Integer.toBinaryString(n).toCharArray();
        int length = arr.length;
        char item = '0';
        for (int i = length - 1; i >= 0; i--) {
            char v = arr[i];
            if (v == '1' && item == '1') {
                arr[i] = '0';
                continue;
            }
            if (v == '1' || item == '1') {
                arr[i] = '1';
                item = ((length - i) & 1) == 0 ? '1' : '0';
            }
        }
        if (item == '0') {
            return String.valueOf(arr);
        }
        if ((length & 1) == 1) {
            return "11" + String.valueOf(arr);
        }
        return "1" + String.valueOf(arr);
    }


    public String baseNeg21(int N) {
        //a = -b * c + d -> a = -b * (c + 1) + d + b;
        if (N == 0) return "0";
        StringBuilder res = new StringBuilder();
        while (N != 0) {
            int r = N % -2;
            res.append(r == -1 ? 1 : r);
            N /= -2;
            if (r == -1) N++;
        }
        return res.reverse().toString();
    }


}
